{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving flow shop scheduling problem with genetic algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*POLab* <br>\n",
    "*[cheng-man wu](https://www.linkedin.com/in/chengmanwu)*<br>\n",
    "*2018/07*\n",
    "<br>\n",
    "\n",
    "## ✒️  問題描述 <br>\n",
    "\n",
    "這裡要來說明如何運用 GA 來求解 flow shop的問題，以下將先對 flow shop 問題做個簡介，說明一下編碼原則，接著根據每個程式區塊進行說明\n",
    "\n",
    "### 🔽 什麼是 flow shop 問題? <br>\n",
    "\n",
    "簡單來說，flow shop 問題就是有 n 個工件以及 m 台機台，每個工件在機台的加工順序都一樣，如下圖所示，工件1先進入機台1加工，再到機台2加工，而工件2跟隨著工件1的腳步，按照同樣的機台順序加工，其他工件以此類推。\n",
    "\n",
    "<br>\n",
    "<div align=center>\n",
    "<img src=\"http://localhost:8888/view/Documents/GitHub/Genetic-Algorithm-for-Job-Shop-Scheduling-and-NSGA-II/implementation%20with%20python/GA-flowshop/picture/1.png\" width=\"250\" height=\"500\">\n",
    "</div>\n",
    "<br>\n",
    "\n",
    "因此假設現在有3個工件2台機台，每個工件在每台機台的加工時間，如左下圖所示，工件的加工順序為先到機台A加工再到機台B，假設得到的排程結果為<br>\n",
    "Job 1->Job 2->Job 3，因此可得到如右下圖的甘特圖\n",
    "\n",
    "<br>\n",
    "<div align=center>\n",
    "<img src=\"http://localhost:8888/view/Documents/GitHub/Genetic-Algorithm-for-Job-Shop-Scheduling-and-NSGA-II/implementation%20with%20python/GA-flowshop/picture/2.png\" width=\"250\" height=\"500\">\n",
    "</div>\n",
    "<br>\n",
    "### 🔽 本範例 flow shop 的排程目標 <br>\n",
    "\n",
    "在本文章中所示範的 flow shop 問題，**目標為最小化總加權延遲 (Total weighted tardiness)**，因此除了必須知道每個工件在每台機台上的加工時間外，還必須知道每個工件的到期日及權重。<br>\n",
    "\n",
    "總加權延遲時間的公式如下：<br>\n",
    "\n",
    "c<sub>i</sup></sub>：工件i的完工時間(Completion time)、d<sub>i</sup></sub>：工件i的到期日(Due date)、T<sub>i</sup></sub>：工件i的延遲時間(Tardiness time)、w<sub>i</sup></sub>：工件i的權重(Weight) \n",
    "- 首先計算每個工件的延遲時間，如果提早做完，則延遲時間為0 <br>\n",
    "\n",
    "$$\n",
    "\\begin{array}{c}\n",
    "T_i&=&\\max\\{0,c_i-d_i\\} \\\\\\\n",
    "\\end{array}\n",
    "$$\n",
    "- 計算所有工件的加權延遲時間總和，從公式我們可以知道，當工件的權重越大，我們要盡可能的準時完成那些權重較大的工件，不然會導致總加權延遲時間太大，對於這樣的排程目標問題來說，這就不是一個好的排程\n",
    "\n",
    "\\begin{equation*}\n",
    "\\left( \\sum_{i=1}^n w_i T_i \\right)\n",
    "\\end{equation*}\n",
    "\n",
    "另外，這裡還有提供另一個版本的 flow shop 程式，跟本文主要的差別在於求解目標的不同，另一版本的目標為最小化總閒置時間 (Idle time)，也就是上面範例甘特圖中，灰色區域的部分，期望排出來的排程，可以盡可能減少總機台的閒置時間。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔽 編碼原則  <br>\n",
    "\n",
    "這裡的編碼方式很簡單，每個染色體就表示一組排程結果，因此，如果 flow shop 的問題中，共有五個工件要排，則每個染色體就由五個基因所組成，每個基因即代表某個工件，在程式裡，會透過 list 來儲存每個染色體，如下面所示：<br>\n",
    "\n",
    "chromosome 1 => [0,1,2,3,4] <br>\n",
    "chromosome 2 => [1,2,0,3,4] <br>\n",
    "chromosome 2 => [4,2,0,1,3] <br>\n",
    "........<br>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ✒️  程式說明 <br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔽 導入所需套件 <br>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# importing required modules\n",
    "#import os\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔽 初始設定 <br>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please input the size of population: \n",
      "Please input the size of Crossover Rate: \n",
      "Please input the size of Mutation Rate: \n",
      "Please input the mutation selection rate: \n",
      "Please input number of iteration: \n"
     ]
    }
   ],
   "source": [
    "''' ================= initialization setting ======================'''\n",
    "num_job=20 # number of jobs\n",
    "\n",
    "p=[10,10,13,4,9,4,8,15,7,1,9,3,15,9,11,6,5,14,18,3]\n",
    "d=[50,38,49,12,20,105,73,45,6,64,15,6,92,43,78,21,15,50,150,99]\n",
    "w=[10,5,1,5,10,1,5,10,5,1,5,10,10,5,1,10,5,5,1,5]\n",
    "# raw_input is used in python 2\n",
    "population_size=int(input('Please input the size of population: ') or 30) # default value is 30\n",
    "crossover_rate=float(input('Please input the size of Crossover Rate: ') or 0.8) # default value is 0.8\n",
    "mutation_rate=float(input('Please input the size of Mutation Rate: ') or 0.1) # default value is 0.1\n",
    "mutation_selection_rate=float(input('Please input the mutation selection rate: ') or 0.5)\n",
    "num_mutation_jobs=round(num_job*mutation_selection_rate)\n",
    "num_iteration=int(input('Please input number of iteration: ') or 2000) # default value is 2000\n",
    "\n",
    "\n",
    "start_time = time.time()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔽 產生初始解 <br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "'''----- generate initial population -----'''\n",
    "Tbest=999999999999999\n",
    "best_list,best_obj=[],[]\n",
    "population_list=[]\n",
    "for i in range(population_size):\n",
    "    nxm_random_num=list(np.random.permutation(num_job)) # generate a random permutation of 0 to num_job*num_mc-1\n",
    "    population_list.append(nxm_random_num) # add to the population_list\n",
    "        \n",
    "for n in range(num_iteration):\n",
    "    Tbest_now=99999999999 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔽 交配 <br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    '''-------- crossover --------'''\n",
    "    parent_list=population_list[:]\n",
    "    offspring_list=population_list[:]\n",
    "    S=list(np.random.permutation(population_size)) # generate a random sequence to select the parent chromosome to crossover\n",
    "    \n",
    "    for m in range(int(population_size/2)):\n",
    "        crossover_prob=np.random.rand()\n",
    "        if crossover_rate>=crossover_prob:\n",
    "            parent_1= population_list[S[2*m]][:]\n",
    "            parent_2= population_list[S[2*m+1]][:]\n",
    "            child_1=['na' for i in range(num_job)]\n",
    "            child_2=['na' for i in range(num_job)]\n",
    "            fix_num=round(num_job/2)\n",
    "            g_fix=list(np.random.choice(num_job, fix_num, replace=False))\n",
    "            \n",
    "            for g in range(fix_num):\n",
    "                child_1[g_fix[g]]=parent_2[g_fix[g]]\n",
    "                child_2[g_fix[g]]=parent_1[g_fix[g]]\n",
    "            c1=[parent_1[i] for i in range(num_job) if parent_1[i] not in child_1]\n",
    "            c2=[parent_2[i] for i in range(num_job) if parent_2[i] not in child_2]\n",
    "            \n",
    "            for i in range(num_job-fix_num):\n",
    "                child_1[child_1.index('na')]=c1[i]\n",
    "                child_2[child_2.index('na')]=c2[i]\n",
    "            offspring_list[S[2*m]]=child_1[:]\n",
    "            offspring_list[S[2*m+1]]=child_2[:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔽 突變<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    '''--------mutatuon--------'''   \n",
    "    for m in range(len(offspring_list)):\n",
    "        mutation_prob=np.random.rand()\n",
    "        if mutation_rate >= mutation_prob:\n",
    "            m_chg=list(np.random.choice(num_job, num_mutation_jobs, replace=False)) # chooses the position to mutation\n",
    "            t_value_last=offspring_list[m][m_chg[0]] # save the value which is on the first mutation position\n",
    "            for i in range(num_mutation_jobs-1):\n",
    "                offspring_list[m][m_chg[i]]=offspring_list[m][m_chg[i+1]] # displacement\n",
    "            \n",
    "            offspring_list[m][m_chg[num_mutation_jobs-1]]=t_value_last # move the value of the first mutation position to the last mutation position\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔽 適應值計算<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    '''--------fitness value(calculate tardiness)-------------'''\n",
    "    total_chromosome=parent_list[:]+offspring_list[:] # combine parent and offspring chromosomes\n",
    "    chrom_fitness,chrom_fit=[],[]\n",
    "    total_fitness=0\n",
    "    for i in range(population_size*2):\n",
    "        ptime=0\n",
    "        tardiness=0\n",
    "        for j in range(num_job):\n",
    "            ptime=ptime+p[total_chromosome[i][j]]\n",
    "            tardiness=tardiness+w[total_chromosome[i][j]]*max(ptime-d[total_chromosome[i][j]],0)\n",
    "        chrom_fitness.append(1/tardiness)\n",
    "        chrom_fit.append(tardiness)\n",
    "        total_fitness=total_fitness+chrom_fitness[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔽 選擇 <br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    '''----------selection----------'''\n",
    "    pk,qk=[],[]\n",
    "    \n",
    "    for i in range(population_size*2):\n",
    "        pk.append(chrom_fitness[i]/total_fitness)\n",
    "    for i in range(population_size*2):\n",
    "        cumulative=0\n",
    "        for j in range(0,i+1):\n",
    "            cumulative=cumulative+pk[j]\n",
    "        qk.append(cumulative)\n",
    "    \n",
    "    selection_rand=[np.random.rand() for i in range(population_size)]\n",
    "    \n",
    "    for i in range(population_size):\n",
    "        if selection_rand[i]<=qk[0]:\n",
    "            population_list[i][:]=total_chromosome[0][:]\n",
    "            break\n",
    "        else:\n",
    "            for j in range(0,population_size*2-1):\n",
    "                if selection_rand[i]>qk[j] and selection_rand[i]<=qk[j+1]:\n",
    "                    population_list[i][:]=total_chromosome[j+1][:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔽 比較<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    '''----------comparison----------'''\n",
    "    for i in range(population_size*2):\n",
    "        if chrom_fit[i]<Tbest_now:\n",
    "            Tbest_now=chrom_fit[i]\n",
    "            sequence_now=total_chromosome[i][:]\n",
    "    \n",
    "    if Tbest_now<=Tbest:\n",
    "        Tbest=Tbest_now\n",
    "        sequence_best=sequence_now[:]\n",
    "    \n",
    "    job_sequence_ptime=0\n",
    "    num_tardy=0\n",
    "    for k in range(num_job):\n",
    "        job_sequence_ptime=job_sequence_ptime+p[sequence_best[k]]\n",
    "        if job_sequence_ptime>d[sequence_best[k]]:\n",
    "            num_tardy=num_tardy+1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔽 結果<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimeal sequence [15, 16, 17, 6, 10, 4, 7, 0, 11, 12, 1, 2, 13, 19, 8, 14, 3, 9, 18, 5]\n",
      "optimeal value:3526.000000\n",
      "average tardiness:176.300000\n",
      "number of tardy:16\n",
      "the elapsed time:19.531383752822876\n"
     ]
    }
   ],
   "source": [
    "'''----------result----------'''\n",
    "print(\"optimeal sequence\",sequence_best)\n",
    "print(\"optimeal value:%f\"%Tbest)\n",
    "print(\"average tardiness:%f\"%(Tbest/num_job))\n",
    "print(\"number of tardy:%d\"%num_tardy)\n",
    "print('the elapsed time:%s'% (time.time() - start_time))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔽 甘特圖<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe id=\"igraph\" scrolling=\"no\" style=\"border:none;\" seamless=\"seamless\" src=\"https://plot.ly/~ftcu5931/52.embed\" height=\"600px\" width=\"900px\"></iframe>"
      ],
      "text/plain": [
       "<plotly.tools.PlotlyDisplay object>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''--------plot gantt chart-------'''\n",
    "import pandas as pd\n",
    "import plotly.plotly as py\n",
    "import plotly.figure_factory as ff\n",
    "import plotly.offline as offline\n",
    "import datetime\n",
    "\n",
    "j_keys=[j for j in range(num_job)]\n",
    "j_count={key:0 for key in j_keys}\n",
    "m_count=0\n",
    "j_record={}\n",
    "for i in sequence_best:\n",
    "   gen_t=int(p[i])\n",
    "   j_count[i]=j_count[i]+gen_t\n",
    "   m_count=m_count+gen_t\n",
    "   \n",
    "   if m_count<j_count[i]:\n",
    "       m_count=j_count[i]\n",
    "   elif m_count>j_count[i]:\n",
    "       j_count[i]=m_count\n",
    "   start_time=str(datetime.timedelta(seconds=j_count[i]-p[i])) # convert seconds to hours, minutes and seconds\n",
    "\n",
    "   end_time=str(datetime.timedelta(seconds=j_count[i]))\n",
    "   j_record[i]=[start_time,end_time]\n",
    "       \n",
    "\n",
    "df=[]\n",
    "for j in j_keys:\n",
    "   df.append(dict(Task='Machine', Start='2018-07-14 %s'%(str(j_record[j][0])), Finish='2018-07-14 %s'%(str(j_record[j][1])),Resource='Job %s'%(j+1)))\n",
    "\n",
    "# colors={}\n",
    "# for i in j_keys:\n",
    "#     colors['Job %s'%(i+1)]='rgb(%s,%s,%s)'%(255/(i+1)+0*i,5+12*i,50+10*i)\n",
    "\n",
    "fig = ff.create_gantt(df, colors=['#008B00','#FF8C00','#E3CF57','#0000CD','#7AC5CD','#ED9121','#76EE00','#6495ED','#008B8B','#A9A9A9','#A2CD5A','#9A32CD','#8FBC8F','#EEC900','#EEE685','#CDC1C5','#9AC0CD','#EEA2AD','#00FA9A','#CDB38B'], index_col='Resource', show_colorbar=True, group_tasks=True, showgrid_x=True)\n",
    "py.iplot(fig, filename='GA_flow_shop_scheduling_tardyjob', world_readable=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "'''\n",
    "Author: cheng-man wu\n",
    "LinkedIn: www.linkedin.com/in/chengmanwu\n",
    "Github: https://github.com/wurmen\n",
    "\n",
    "==============================================================\n",
    "Soving single-machine total weighted tardiness problem. \n",
    "The objective function is to minimize the total weighted tardiness. \n",
    "==============================================================\n",
    "\n",
    "'''\n",
    "# importing required modules\n",
    "#import os\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import time\n",
    "\n",
    "\n",
    "''' ================= initialization setting ======================'''\n",
    "num_job=20 # number of jobs\n",
    "\n",
    "p=[10,10,13,4,9,4,8,15,7,1,9,3,15,9,11,6,5,14,18,3]\n",
    "d=[50,38,49,12,20,105,73,45,6,64,15,6,92,43,78,21,15,50,150,99]\n",
    "w=[10,5,1,5,10,1,5,10,5,1,5,10,10,5,1,10,5,5,1,5]\n",
    "# raw_input is used in python 2\n",
    "population_size=int(input('Please input the size of population: ') or 30) # default value is 30\n",
    "crossover_rate=float(input('Please input the size of Crossover Rate: ') or 0.8) # default value is 0.8\n",
    "mutation_rate=float(input('Please input the size of Mutation Rate: ') or 0.1) # default value is 0.1\n",
    "mutation_selection_rate=float(input('Please input the mutation selection rate: ') or 0.5)\n",
    "num_mutation_jobs=round(num_job*mutation_selection_rate)\n",
    "num_iteration=int(input('Please input number of iteration: ') or 2000) # default value is 2000\n",
    "\n",
    "\n",
    "start_time = time.time()\n",
    "\n",
    "'''==================== main code ==============================='''\n",
    "'''----- generate initial population -----'''\n",
    "Tbest=999999999999999\n",
    "best_list,best_obj=[],[]\n",
    "population_list=[]\n",
    "for i in range(population_size):\n",
    "    nxm_random_num=list(np.random.permutation(num_job)) # generate a random permutation of 0 to num_job*num_mc-1\n",
    "    population_list.append(nxm_random_num) # add to the population_list\n",
    "        \n",
    "for n in range(num_iteration):\n",
    "    Tbest_now=99999999999           \n",
    "    '''-------- crossover --------'''\n",
    "    parent_list=population_list[:]\n",
    "    offspring_list=population_list[:]\n",
    "    S=list(np.random.permutation(population_size)) # generate a random sequence to select the parent chromosome to crossover\n",
    "    \n",
    "    for m in range(int(population_size/2)):\n",
    "        crossover_prob=np.random.rand()\n",
    "        if crossover_rate>=crossover_prob:\n",
    "            parent_1= population_list[S[2*m]][:]\n",
    "            parent_2= population_list[S[2*m+1]][:]\n",
    "            child_1=['na' for i in range(num_job)]\n",
    "            child_2=['na' for i in range(num_job)]\n",
    "            fix_num=round(num_job/2)\n",
    "            g_fix=list(np.random.choice(num_job, fix_num, replace=False))\n",
    "            \n",
    "            for g in range(fix_num):\n",
    "                child_1[g_fix[g]]=parent_2[g_fix[g]]\n",
    "                child_2[g_fix[g]]=parent_1[g_fix[g]]\n",
    "            c1=[parent_1[i] for i in range(num_job) if parent_1[i] not in child_1]\n",
    "            c2=[parent_2[i] for i in range(num_job) if parent_2[i] not in child_2]\n",
    "            \n",
    "            for i in range(num_job-fix_num):\n",
    "                child_1[child_1.index('na')]=c1[i]\n",
    "                child_2[child_2.index('na')]=c2[i]\n",
    "            offspring_list[S[2*m]]=child_1[:]\n",
    "            offspring_list[S[2*m+1]]=child_2[:]\n",
    "        \n",
    "    '''--------mutatuon--------'''   \n",
    "    for m in range(len(offspring_list)):\n",
    "        mutation_prob=np.random.rand()\n",
    "        if mutation_rate >= mutation_prob:\n",
    "            m_chg=list(np.random.choice(num_job, num_mutation_jobs, replace=False)) # chooses the position to mutation\n",
    "            t_value_last=offspring_list[m][m_chg[0]] # save the value which is on the first mutation position\n",
    "            for i in range(num_mutation_jobs-1):\n",
    "                offspring_list[m][m_chg[i]]=offspring_list[m][m_chg[i+1]] # displacement\n",
    "            \n",
    "            offspring_list[m][m_chg[num_mutation_jobs-1]]=t_value_last # move the value of the first mutation position to the last mutation position\n",
    "    \n",
    "    \n",
    "    '''--------fitness value(calculate tardiness)-------------'''\n",
    "    total_chromosome=parent_list[:]+offspring_list[:] # combine parent and offspring chromosomes\n",
    "    chrom_fitness,chrom_fit=[],[]\n",
    "    total_fitness=0\n",
    "    for i in range(population_size*2):\n",
    "        ptime=0\n",
    "        tardiness=0\n",
    "        for j in range(num_job):\n",
    "            ptime=ptime+p[total_chromosome[i][j]]\n",
    "            tardiness=tardiness+w[total_chromosome[i][j]]*max(ptime-d[total_chromosome[i][j]],0)\n",
    "        chrom_fitness.append(1/tardiness)\n",
    "        chrom_fit.append(tardiness)\n",
    "        total_fitness=total_fitness+chrom_fitness[i]\n",
    "    \n",
    "    '''----------selection----------'''\n",
    "    pk,qk=[],[]\n",
    "    \n",
    "    for i in range(population_size*2):\n",
    "        pk.append(chrom_fitness[i]/total_fitness)\n",
    "    for i in range(population_size*2):\n",
    "        cumulative=0\n",
    "        for j in range(0,i+1):\n",
    "            cumulative=cumulative+pk[j]\n",
    "        qk.append(cumulative)\n",
    "    \n",
    "    selection_rand=[np.random.rand() for i in range(population_size)]\n",
    "    \n",
    "    for i in range(population_size):\n",
    "        if selection_rand[i]<=qk[0]:\n",
    "            population_list[i][:]=total_chromosome[0][:]\n",
    "            break\n",
    "        else:\n",
    "            for j in range(0,population_size*2-1):\n",
    "                if selection_rand[i]>qk[j] and selection_rand[i]<=qk[j+1]:\n",
    "                    population_list[i][:]=total_chromosome[j+1][:]\n",
    "            \n",
    "    '''----------comparison----------'''\n",
    "    for i in range(population_size*2):\n",
    "        if chrom_fit[i]<Tbest_now:\n",
    "            Tbest_now=chrom_fit[i]\n",
    "            sequence_now=total_chromosome[i][:]\n",
    "    \n",
    "    if Tbest_now<=Tbest:\n",
    "        Tbest=Tbest_now\n",
    "        sequence_best=sequence_now[:]\n",
    "    \n",
    "    job_sequence_ptime=0\n",
    "    num_tardy=0\n",
    "    for k in range(num_job):\n",
    "        job_sequence_ptime=job_sequence_ptime+p[sequence_best[k]]\n",
    "        if job_sequence_ptime>d[sequence_best[k]]:\n",
    "            num_tardy=num_tardy+1\n",
    "'''----------result----------'''\n",
    "print(\"optimeal sequence\",sequence_best)\n",
    "print(\"optimeal value:%f\"%Tbest)\n",
    "print(\"average tardiness:%f\"%(Tbest/num_job))\n",
    "print(\"number of tardy:%d\"%num_tardy)\n",
    "print('the elapsed time:%s'% (time.time() - start_time))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe id=\"igraph\" scrolling=\"no\" style=\"border:none;\" seamless=\"seamless\" src=\"https://plot.ly/~ftcu5931/52.embed\" height=\"600px\" width=\"900px\"></iframe>"
      ],
      "text/plain": [
       "<plotly.tools.PlotlyDisplay object>"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''--------plot gantt chart-------'''\n",
    "import pandas as pd\n",
    "import plotly.plotly as py\n",
    "import plotly.figure_factory as ff\n",
    "import plotly.offline as offline\n",
    "import datetime\n",
    "\n",
    "j_keys=[j for j in range(num_job)]\n",
    "j_count={key:0 for key in j_keys}\n",
    "m_count=0\n",
    "j_record={}\n",
    "for i in sequence_best:\n",
    "   gen_t=int(p[i])\n",
    "   j_count[i]=j_count[i]+gen_t\n",
    "   m_count=m_count+gen_t\n",
    "   \n",
    "   if m_count<j_count[i]:\n",
    "       m_count=j_count[i]\n",
    "   elif m_count>j_count[i]:\n",
    "       j_count[i]=m_count\n",
    "   start_time=str(datetime.timedelta(seconds=j_count[i]-p[i])) # convert seconds to hours, minutes and seconds\n",
    "\n",
    "   end_time=str(datetime.timedelta(seconds=j_count[i]))\n",
    "   j_record[i]=[start_time,end_time]\n",
    "       \n",
    "\n",
    "df=[]\n",
    "for j in j_keys:\n",
    "   df.append(dict(Task='Machine', Start='2018-07-14 %s'%(str(j_record[j][0])), Finish='2018-07-14 %s'%(str(j_record[j][1])),Resource='Job %s'%(j+1)))\n",
    "\n",
    "# colors={}\n",
    "# for i in j_keys:\n",
    "#     colors['Job %s'%(i+1)]='rgb(%s,%s,%s)'%(255/(i+1)+0*i,5+12*i,50+10*i)\n",
    "\n",
    "fig = ff.create_gantt(df, colors=['#008B00','#FF8C00','#E3CF57','#0000CD','#7AC5CD','#ED9121','#76EE00','#6495ED','#008B8B','#A9A9A9','#A2CD5A','#9A32CD','#8FBC8F','#EEC900','#EEE685','#CDC1C5','#9AC0CD','#EEA2AD','#00FA9A','#CDB38B'], index_col='Resource', show_colorbar=True, group_tasks=True, showgrid_x=True)\n",
    "py.iplot(fig, filename='GA_flow_shop_scheduling_tardyjob', world_readable=True)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
